//给定一个二叉树，检查它是否是镜像对称的。 
//
// 
//
// 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。 
//
//     1
//   / \
//  2   2
// / \ / \
//3  4 4  3
// 
//
// 
//
// 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的: 
//
//     1
//   / \
//  2   2
//   \   \
//   3    3
// 
//
// 
//
// 进阶： 
//
// 你可以运用递归和迭代两种方法解决这个问题吗？ 
// Related Topics 树 深度优先搜索 广度优先搜索 
// 👍 1211 👎 0

package leetcode.editor.cn;
//Java：对称二叉树
public class SymmetricTree{
    public static void main(String[] args) {
        Solution solution = new SymmetricTree().new Solution();
        
    }
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
    Definition for a binary tree node.
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if ( root == null ){
            return true;
        }
        return dfs(root.left, root.right);
    }

    private boolean dfs(TreeNode leftNode, TreeNode rightNode) {
        //都是空节点
        if ( leftNode == null && rightNode == null  ){
            return true;
        }
        //有一个是空节点
        if ( leftNode == null || rightNode == null  ){
            return false;
        }
        //值不对
        if ( leftNode.val != rightNode.val ){
            return false;
        }
        //左孩子的右孩子节点和右孩子的左孩子节点
        //左孩子的左孩子节点和右孩子的右孩子节点
        return dfs( leftNode.right, rightNode.left ) && dfs( leftNode.left, rightNode.right);
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
